{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 机器学习\n",
    "***\n",
    "Time: 2020-09-08<br>\n",
    "Author: dsy\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 聚类\n",
    "#### 1.1 请问从EM角度理解kmeans?\n",
    "- k-means是两个步骤交替进行，可以分别看成E步和M步\n",
    "- M步中将每类的中心更新为分给该类各点的均值，可以认为是在「各类分布均为单位方差的高斯分布」的假设下，最大化似然值；\n",
    "- E步中将每个点分给中心距它最近的类（硬分配），可以看成是EM算法中E步（软分配）的近似\n",
    "\n",
    "#### 1.2 为什么kmeans一定会收敛?\n",
    "M步中的最大化似然值，更新参数依赖的是MSE，MSE至少存在局部最优解，必然收敛\n",
    "\n",
    "#### 1.3 kmeans初始点除了随机选取之外的方法？\n",
    "先层次聚类，再在不同层次上选取初始点进行kmeans聚类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K-Means 聚类算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def dist(x1,x2):\n",
    "    return ((x1 - x2) ** 2).sum()\n",
    "\n",
    "def KMeans(x,k,iters=1000):\n",
    "    '''\n",
    "    \n",
    "    K-Means聚类的思想：\n",
    "        选取k个类中心，然后更新每一个x到类中距离，选取最短的距离作为该x的分类\n",
    "    params:\n",
    "        x: 数据集\n",
    "        k：类别数\n",
    "    Author: \n",
    "        dsy\n",
    "    '''\n",
    "    m = x[:k]\n",
    "    G = None\n",
    "    \n",
    "    for each in range(iters):\n",
    "        G = [[] for i in range(k)]\n",
    "        for i in range(len(X)):\n",
    "            d = [dist(x[i],m[j]) for j in range(k)] # 计算距离\n",
    "            G[d.index(min(d))].append( x[i].tolist()) # 聚类结果\n",
    "        m = [np.array(G[i]).mean(axis=0) for i in range(len(G))]  #更新类中心\n",
    "        \n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[[0, 2], [5, 2]], [[0, 0], [1, 0], [5, 0]]]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = np.array([\n",
    "    [0,2],\n",
    "    [0,0],\n",
    "    [1,0],\n",
    "    [5,0],\n",
    "    [5,2]\n",
    "])\n",
    "KMeans(X,2,iters=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EM算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def EM(Π,p,q,data):\n",
    "    '''\n",
    "    params:\n",
    "        Π ： A的概率\n",
    "        p ： B的概率\n",
    "        q ： C的概率\n",
    "        data: 观测数据\n",
    "    return:\n",
    "        Π,p,q\n",
    "    '''\n",
    "    # E Step\n",
    "    def μ(i,A,B,C):\n",
    "        return A * math.pow(B,data[i]) * math.pow(1-B,1 - data[i]) / (A * math.pow(B,data[i]) * math.pow(1-B,1 - data[i]) + (1 - A) * math.pow(C,data[i]) * math.pow(1-C,1 - data[i]))\n",
    "    \n",
    "    n = len(data)\n",
    "    # M Step\n",
    "    for i in range(n):\n",
    "        Π = 1./n * sum([μ(i,Π,p,q) for k in range(n)])\n",
    "        \n",
    "        p = sum([μ(i,Π,p,q) * data[k] for k in range(n)]) / sum([μ(i,Π,p,q) for k in range(n)])\n",
    "        \n",
    "        q =  sum([(1 - μ(i,Π,p,q)) * data[k] for k in range(n)]) / sum([(1 - μ(i,Π,p,q)) for k in range(n)])\n",
    "        \n",
    "        print(\"迭代了\",i+1,\"次的\",\"Π=%.3f ,p=%.3f ,q=%.3f\" % (Π,p,q))\n",
    "    \n",
    "    return (Π,p,q)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "迭代了 1 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 2 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 3 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 4 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 5 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 6 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 7 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 8 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 9 次的 Π=0.500 ,p=0.600 ,q=0.600\n",
      "迭代了 10 次的 Π=0.500 ,p=0.600 ,q=0.600\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(0.5000000000000001, 0.6, 0.6)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EM(0.5,0.5,0.5,[1,1,0,1,0,0,1,0,1,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 线性回归\n",
    "#### 2.1 损失函数是啥\n",
    "mse,最小均方误差:\n",
    "$$\n",
    "J(\\theta) = \\frac{1}{m}\\sum_{i=1}^{m}\\big( h_\\theta(x^i)-y^i\\big)^2\n",
    "$$\n",
    "\n",
    "#### 2.2 最小二乘/梯度下降手推\n",
    "- 最小二乘\n",
    "    - 损失函数：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93458dklvj306l011t8j.jpg)\n",
    "    - 求导可得：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93489pnxxj3052014jr7.jpg)\n",
    "        - 使右侧为0可得：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g934a6q83tj304300kdfm.jpg) \n",
    "        - 如果X点乘X的转置可逆则有唯一解，否则无法如此求解\n",
    "- 梯度下降\n",
    "    - 损失函数：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g933uf4aimj305u01fa9w.jpg)\n",
    "    - 求导可得梯度：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g934mwtnodj307401fdfp.jpg)\n",
    "    \n",
    "#### 2.3 介绍一下岭回归\n",
    "加上l2的线性回归：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g934px37g4j305b017glf.jpg)\n",
    "\n",
    "在用最小二乘推导的过程和上面一样，最后在结果上进行了平滑，保证有解：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g934t64beij304w00kmwy.jpg)\n",
    "    \n",
    "\n",
    "#### 2.4 什么时候使用岭回归？\n",
    "样本数少，或者样本重复程度高\n",
    "\n",
    "> 简单来说：岭回归就是在矩阵$x^Tx$上加一个$\\lambda I $从而使得矩阵非奇异，进而能对$x^Tx+\\lambda I$求逆。其中矩阵$I$是一个$mxm$的单位矩阵，对角线上元素全为1，其他元素全为0。$\\lambda$是用户定义的数值。\n",
    "\n",
    "#### 2.5 什么时候用Lasso回归？    \n",
    "特征过多，稀疏线性关系，目的为了在一堆特征里面找出主要的特征"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 逻辑回归\n",
    "#### 3.1 logistic分布函数和密度函数，手绘大概的图像\n",
    "- 分布函数：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93b9whhwuj306z01amwz.jpg)\n",
    "- 密度函数：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93bdnikzbj306e01pjr8.jpg)\n",
    "- 其中，μ表示位置参数，γ为形状参数。**logistic分布比正太分布有更长的尾部且波峰更尖锐**\n",
    "\n",
    "#### 3.2 LR推导，基础5连问\n",
    "- 基础公式\n",
    "    - f(x) = wx + b\n",
    "    - y = sigmoid(f(x))\n",
    "    - 可以看作是一次线性拟合+一次sigmoid的非线性变化\n",
    "- 伯努利过程\n",
    "    - 对于lr来说事情只有发生和不发生两种可能，对于已知样本来说，满足伯努利的概率假设：\n",
    "        - p(y=1/x,θ) = h(θ,x)\n",
    "        - p(y=0/x,θ) = 1-h(θ,x)\n",
    "        - p(y/x,θ) = h(θ,x)^y · (1-h(θ,x))^(1-y) \n",
    "            - 第i个样本正确预测的概率如上可得\n",
    "    - 几率odds\n",
    "        - 数据特征下属于正例及反例的比值\n",
    "        - ln(y/(1-y))\n",
    "- 极大似然\n",
    "    - 第i个样本正确预测的概率如上可得每条样本的情况下\n",
    "    - 综合全部样本发生的概率都要最大的话，采取极大似然连乘可得：\n",
    "        - ∏(h(θ,x)^y · (1-h(θ,x))^(1-y))\n",
    "- 损失函数\n",
    "    - 通常会对极大似然取对数，得到损失函数，方便计算\n",
    "        - ∑ylogh(θ,x)+(1-y)log(1-h(θ,x))最大\n",
    "        - 及-1/m · ∑ylogh(θ,x)+(1-y)log(1-h(θ,x))最小    \n",
    "- 梯度下降\n",
    "    - 损失函数求偏导，更新θ\n",
    "    - θj+1 = θj - ∆·∂Loss/∂θ =θj - ∆·1/m·∑x·(h-y)\n",
    "        - ∆为学习率\n",
    "\n",
    "#### 3.3 梯度下降如何并行化？\n",
    "- 首先需要理解梯度下降的更新公式：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93cn8ok1fj307a01ft8k.jpg)\n",
    "    - ∑处的并行，不同样本在不同机器上进行计算，计算完再进行合并\n",
    "    - 同一条样本不同特征维度进行拆分，![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93cnjne2dj303200ia9u.jpg)处并行，把![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93csl2l0pj301400ia9t.jpg)内的xi和Wi拆分成块分别计算后合并，再把外层![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93cnjne2dj303200ia9u.jpg)同样拆分成若干块进行计算\n",
    "\n",
    "#### 3.4 LR明明是分类模型为什么叫回归？\n",
    "观测样本中该特征在正负类中出现概率的比值满足线性条件，用的是线性拟合比率值，所以叫回归\n",
    "\n",
    "#### 3.5 为什么LR可以用来做CTR预估？\n",
    "1. 点击行为为正向，未点击行为为负向，ctr需要得到点击行为的概率，lr可以产出正向行为的概率，完美match\n",
    "2. 实现简单，方便并行，计算迭代速度很快\n",
    "3. 可解释性强，可结合正则化等优化方法\n",
    "\n",
    "#### 3.6 满足什么样条件的数据用LR最好？\n",
    "- 特征之间尽可能独立\n",
    "    - 不独立所以我们把不独立的特征交叉了\n",
    "        - 还记得FM的思路？\n",
    "- 离散特征\n",
    "    - 连续特征通常没有特别含义，31岁和32岁差在哪？\n",
    "    - 离散特征方便交叉考虑\n",
    "    - 在异常值处理上也更加方便\n",
    "    - 使的lr满足分布假设\n",
    "        - 什么分布假设？\n",
    "- 在某种确定分类上的特征分布满足高斯分布\n",
    "    - ![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wh7dd6bkj310w034gmb.jpg)\n",
    "    - C1和C2为正负类，观测样本中该特征在正负类中出现概率的比值满足线性条件的前提就是P服从正太分布\n",
    "        - 实际中不满足的很多，不满足我们通常就离散化，oneHotEncode\n",
    "\n",
    "此处就用到了全概率公式推导，有可能会回到[写出全概率公式&贝叶斯公式](https://github.com/sladesha/Reflection_Summary/blob/master/基础概念/先验概率和后验概率/先验概率和后验概率.md#L96)的问题中\n",
    "\n",
    "#### 3.7 LR为什么使用sigmoid函数作为激活函数？其他函数不行吗？\n",
    "- 思路一：lr的前提假设就是几率odds满足线性回归，odds又为正负样本的log比，参见`满足什么样条件的数据用LR最好？`中第三点公式的展开\n",
    "- 思路二：Exponential model 的形式是这样的：假设第i个特征对第k类的贡献是![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wmq11x6zj300s00f3y9.jpg)，则数据点![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wmqpotqfj302700imwx.jpg)属于第k类的概率正比于![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wmrp4qv4j305b00i0sj.jpg)。\n",
    "    - 二分类上：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wmsc1vfkj30jm036wet.jpg)\n",
    "    - 化简即为sigmoid\n",
    "    - 以上思路源自：PRML（Pattern Recognition and Machine Learning）\n",
    "- 思路三：glm有满足指数族的性质，而作为lr作为y满足伯努利分布的的线性条件，伯努利分布的指数族形式就是sigmoid，或者也叫连接函数\n",
    "\n",
    "#### 3.8 利用几率odds的意义在哪？\n",
    "- 直接对分类模型进行建模，前提假设为非常弱的指定类别上自变量的条件分布满足高斯\n",
    "- 由预测0/1的类别扩展到了预测0-1的概率值\n",
    "- 任意阶可导的优秀性质    \n",
    "\n",
    "#### 3.9 Sigmoid函数到底起了什么作用？\n",
    "- 数据规约：\\[0,1]\n",
    "- 线性回归在全量数据上的敏感度一致，sigmoid在分界点0.5处更加敏感    \n",
    "- sigmoid在逻辑回归的参数更新中也不起影响，避免了更新速度不稳定的问题\n",
    "\n",
    "#### 3.10 LR为什么要使用极大似然函数，交互熵作为损失函数？那为什么不选平方损失函数的呢\n",
    "- 更新速度只与真实的x和y相关，与激活函数无关，更新平稳\n",
    "    - 比如mse就会导致更新速度与激活函数sigmoid挂钩，而sigmoid函数在定义域内的梯度大小都比较小(0.25>x)，不利于快速更新\n",
    "    - mse下的lr损失函数非凸，难以得到解析解\n",
    "\n",
    "#### 3.11 LR中若标签为+1和-1，损失函数如何推导？\n",
    "- way1:把0-1的sigmoid的lr结果Y映射为2y-1，推导不变\n",
    "- way2:把激活函数换成tanh，因为tanh的值域范围为\\[-1,1],满足结果，推导不变    \n",
    "- way3:依旧以sigmoid函数的话，似然函数(likelihood)模型是：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wngwzstcj30iu01edfw.jpg)，重复极大似然计算即可    \n",
    "\n",
    "#### 3.12 如果有很多的特征高度相关或者说有一个特征重复了100遍，会造成怎样的影响？\n",
    "#### 3.13 为什么要避免共线性？\n",
    "- 如果在损失函数最终收敛的情况下，其实就算有很多特征高度相关也不会影响分类器的效果\n",
    "- 每一个特征都是原来特征权重值的百分之一，线性可能解释性优点也消失了\n",
    "- 增加训练收敛的难度及耗时，有限次数下可能共线性变量无法收敛，系数估计变得不可靠\n",
    "- 泛化能力变差，训练是两列特征可能会共线性，当线上数据加入噪声后共线性消失，效果可能变差\n",
    "\n",
    "#### 3.14 LR可以用核么？可以怎么用？\n",
    "结论：可以，加l2正则项后可用\n",
    "\n",
    "原因：\n",
    "- 核逻辑回归，需要把拟合参数w表示成z的线性组合及representer theorem理论。这边比较复杂，待更新，需要了解：\n",
    "    - w拆解的z的线性组合中的系数α来源\n",
    "    - representer theorem 的证明\n",
    "        - 凡是进行L2正则化的线性问题我们都能使用核函数的技巧的证明\n",
    "    - 如何将将W*表示成β的形式带到我们最佳化的问题\n",
    "\n",
    "#### 3.15 LR中的L1/L2正则项是啥？\n",
    "- L1正则项：为模型加了一个先验知识，未知参数w满足拉普拉斯分布，![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wpllyoblj303s011gle.jpg) ,u为0。在lr模型损失函数中新增了![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wpimx0juj301g0133ya.jpg)项\n",
    "- L2正则项：为模型加了一个先验知识，未知参数w满足0均值正太分布，![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wpayd8u6j307k0190sl.jpg),u为0。在lr模型损失函数中新增了![](https://tva1.sinaimg.cn/large/006y8mN6gy1g8wpet47boj3011014mwx.jpg)项\n",
    "\n",
    "#### 3.16 lr加l1还是l2好？\n",
    "这个问题还可以换一个说法，l1和l2的各自作用。\n",
    "刚才我们说到l1对未知参数w有个前提假设满足拉普拉斯分布，l2对未知参数的假设则是正太分布，且都是零均值，单纯从图像上我们就可以发现，拉普拉斯对w的规约到0的可能性更高，所以对于特征约束强的需求下l1合适，否则l2    \n",
    "\n",
    "#### 3.17 正则化是依据什么理论实现模型优化？\n",
    "结构风险最小化：在经验风险最小化的基础上（也就是训练误差最小化），尽可能采用简单的模型，以此提高泛化预测精度。\n",
    "\n",
    "#### 3.18 LR可以用来处理非线性问题么？\n",
    "- 特征交叉，类似fm\n",
    "- 核逻辑回归，类似svm\n",
    "- 线性变换+非线性激活，类似neural network\n",
    "\n",
    "#### 3.19 为什么LR需要归一化或者取对数?    \n",
    "**模型中对数据对处理一般都有一个标答是提升数据表达能力，也就是使数据含有的可分信息量更大**\n",
    "- 工程角度：\n",
    "    - 加速收敛\n",
    "    - 提高计算效率\n",
    "- 理论角度:\n",
    "    - 梯度下降过程稳定\n",
    "    - 使得数据在某类上更服从高斯分布，满足前提假设，这个是必须要答出来的\n",
    "    - [归一化和标准化之间的关系](https://github.com/sladesha/Reflection_Summary/blob/master/数据预处理/特征提取/数据变换.md#L6)\n",
    "\n",
    "#### 3.20 为什么LR把特征离散化后效果更好？离散化的好处有哪些？\n",
    "- 原来的单变量可扩展到n个离散变量，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合\n",
    "- 离散后结合正则化可以进行特征筛选，更好防止过拟合\n",
    "- 数据的鲁棒性更好，不会因为无意义的连续值变动导致异常因素的影响，（31岁和32岁的差异在哪呢？）\n",
    "- 离散变量的计算相对于连续变量更快    \n",
    "\n",
    "#### 3.21 逻辑回归估计参数时的目标函数逻辑回归的值表示概率吗？\n",
    "lr的output是彼此之间相对谁的可能性更高，而不是概率，概率是事情发生的可能，lr的output不代表可能    \n",
    "\n",
    "#### 3.22 LR对比万物？\n",
    "- lr和线性回归\n",
    "    - lr解用的极大似然，线性回归用的最小二乘\n",
    "    - lr用于分类，线性回归用于回归\n",
    "    - 但两者都是广义线性回归GLM问题\n",
    "    - 两者对非线性问题的处理能力都是欠佳的\n",
    "\n",
    "- lr和最大熵\n",
    "    - 在解决二分类问题是等同的\n",
    "\n",
    "- lr和svm\n",
    "    - 都可分类，都是判别式模型思路\n",
    "    - 通常都是用正则化进行规约\n",
    "    - 模型上\n",
    "        - lr是交叉熵，svm是HingeLoss\n",
    "        - lr是全量数据拟合，svm是支持向量拟合\n",
    "        - lr是参数估计有参数的前提假设，svm没有\n",
    "        - lr依赖的是极大似然，svm依赖的是距离\n",
    "\n",
    "- lr和朴素贝叶斯\n",
    "    - 如果朴素贝叶斯也有在某一类上的数据x满足高斯分布的假设前提，lr和朴素贝叶斯一致\n",
    "    - lr是判别模型，朴素贝叶斯是生成模型\n",
    "    - lr没有明确feature条件独立(但是不能共线性，理由之前讲了)，朴素贝叶斯要求feature条件独立\n",
    "\n",
    "- lr和最大熵模型\n",
    "    - 本质没有区别\n",
    "    - 最大熵模型在解决二分类问题就是逻辑回归\n",
    "    - 最大熵模型在解决多分类问题的时候就是多项逻辑回归回归\n",
    "\n",
    "#### 3.23 LR梯度下降方法？\n",
    "- 随机梯度下降\n",
    "    - 局部最优解，可跳出鞍点\n",
    "    - 计算快\n",
    "- 批梯度下降\n",
    "    - 全局最优解\n",
    "    - 计算量大\n",
    "- mini批梯度下降\n",
    "    - 综合以上两种方法\n",
    "\n",
    "除此之外，比如ada和冲量梯度下降法会对下降的速率速度进行控制，也会对不同更新速度的参数进行控制，等等，多用于深度学习中\n",
    "\n",
    "#### 3.24 LR的优缺点？\n",
    "- 优点\n",
    "    - 简单，易部署，训练速度快\n",
    "    - 模型下限较高\n",
    "    - 可解释性强\n",
    "- 缺点\n",
    "    - 只能线性可分\n",
    "    - 数据不平衡需要人为处理，weight_class/[有哪些常见的采样方法](https://github.com/sladesha/Reflection_Summary/blob/master/数据预处理/数据平衡/采样.md#L11)\n",
    "    - 模型上限较低\n",
    "\n",
    "#### 3.25 除了做分类，你还会用LR做什么？\n",
    "特征筛选，特征的系数决定该特征的重要性\n",
    "\n",
    "#### 3.26 你有用过sklearn中的lr么？你用的是哪个包？\n",
    "sklearn.linear_model.LogisticRegression\n",
    "\n",
    "#### 3.27 看过源码么？为什么去看？\n",
    "- 看部分参数的解释\n",
    "    - 比如dual、weight_class中的1:0还是0:1比\n",
    "    - 比如输出值的形式，输出的格式\n",
    "\n",
    "#### 3.28 谈一下sklearn.linear_model.LogisticRegression中的penalty和solver的选择？\n",
    "- penalty是正则化，solver是函数优化方法\n",
    "- penalty包含l1和l2两种，solver包含坐标轴下降、牛顿、随机梯度下降等\n",
    "- 牛顿法，拟牛顿法和随机梯度下降都不能使用l1，因为他们都需要损失函数的一阶二阶导数，而坐标轴下降法不限制这些，l1和l2都可行。\n",
    "- l1和l2选择参考上面讲的正则化部分\n",
    "- 随机梯度下降在数据较少的时候最好别用，但是速度比较快。默认的是坐标轴下降法\n",
    "\n",
    "#### 3.29 谈一下sklearn.linear_model.LogisticRegression中对多分类是怎么处理的？\n",
    "- 首先，决定是否为多分类的参数是multi_class\n",
    "- 在二分类的时候，multi和ovr和auto都是一样的\n",
    "- 在真正执行multi的时候，会通过LabelEncoder把目标值y离散化，不停的选择两类去做ovr的计算直到取完所有情况    \n",
    "    \n",
    "#### 3.30 我的总结\n",
    "- 逻辑回归假设观测样本中该特征在正负类中出现结果服从伯努利分布，通过极大化似然函数的方法，运用梯度下降来求解参数，来达到将数据二分类的目的\n",
    "- 逻辑回归本质是线性模型，只能解决线性相关的问题，非线性相关用核或者svm等\n",
    "- 逻辑回归不需要特征的条件独立，但是不能共线性，需要核线性回归一样，做共线性检验\n",
    "- 逻辑回归对样本噪声是鲁棒对，SVM对噪声比较敏感，而logistic回归对噪声不是很敏感，是因为如果噪声点落在了支持向量上，将会直接影响判别面的方程。而logistic回归通过最大似然求解模型参数，将会弱化噪声的影响"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "逻辑回归算法："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以对数似然函数来估计参数：\n",
    "$$\n",
    "L(w) = \\sum_{i=1}^N {[y_i(w \\cdot x_i) - \\log(1+\\exp(w \\cdot x_i))]} \\\\\n",
    "\\frac{\\partial{L(w)} }{\\partial (w)} = \\sum {x \\big(y-\\frac{1}{1+\\exp^{-wx} }\\big)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def LogisticRegression(x,y,iters=1000,learning_rate=0.01):\n",
    "    w = np.zeros((len(x[0]),),dtype=np.float32)\n",
    "    for each in range(iters):\n",
    "        for i in range(len(x)):\n",
    "            w += learning_rate * x[i] * (y[i] - 1. / (1 + np.exp(-w.dot(x[i].T))))\n",
    "            \n",
    "    return w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.  决策树\n",
    "#### 4.1 常见决策树\n",
    "\n",
    "| 模型      | ID3      |     C4.5 |   CART   |\n",
    "| :--------| :-------- | --------:| :------: |\n",
    "| 结构   | 多叉树    |   多叉树 |  二叉树  |\n",
    "| 特征选择   | 信息增益    |   信息增益率 |  Gini系数/均方差  |\n",
    "| 连续值处理   | 不支持    |   支持 |  支持  |\n",
    "| 缺失值处理   | 不支持    |   支持 |  支持  |\n",
    "| 枝剪   | 不支持    |   支持 |  支持  |\n",
    "\n",
    "\n",
    "#### 4.2 简述决策树构建过程\n",
    "1. 构建根节点，将所有训练数据都放在根节点\n",
    "2. 选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类\n",
    "3. 如果子集非空，或子集容量未小于最少数量，递归1，2步骤，直到所有训练数据子集都被正确分类或没有合适的特征为止\n",
    "\n",
    "#### 4.3 详述信息熵计算方法及存在问题\n",
    "![](https://tva1.sinaimg.cn/large/006y8mN6gy1g925k1ns0yj305y018glg.jpg)\n",
    "\n",
    "其中，D为数据全集，C为不同因变量类别k上的子集(传统意义上的y的种类)\n",
    "\n",
    "#### 4.4 详述信息增益计算方法\n",
    "条件信息熵：在特征A给定的条件下对数据集D分类的不确定性：\n",
    "![](https://tva1.sinaimg.cn/large/006y8mN6gy1g925puuv1cj308p01kdfr.jpg)\n",
    "\n",
    "信息增益：知道特征A的信息而使类D的信息的不确定减少的程度（对称）：\n",
    "I(D,A) = H(D)-H(D/A)\n",
    "\n",
    "简而言之，就是在特征A下找到最合适的切分，使得在该切分下信息量的变换最大，更加稳定；但是这个有一个问题，对于类别天生较多的特征，模型更容易选中，因为特征类别较多，切分后的信息增益天生更大，更容易满足我们的原始假设\n",
    "\n",
    "#### 4.5 详述信息增益率计算方法\n",
    "在信息增益计算的基础不变的情况下得到的：I(D,A) = H(D)-H(D/A)，同时还考虑了![](https://tva1.sinaimg.cn/large/006y8mN6gy1g925yr9z1vj306601f745.jpg),用划分的子集数上的熵来平衡了分类数过多的问题。\n",
    "\n",
    "信息增益率：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g9260xx5wej304b017q2r.jpg)\n",
    "\n",
    "#### 4.6 解释Gini系数\n",
    "Gini系数二分情况下：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g92705elt9j308000q744.jpg)\n",
    "\n",
    "对于决策树样本D来说，![](https://tva1.sinaimg.cn/large/006y8mN6gy1g9273px3t2j30a4018wee.jpg)\n",
    "\n",
    "对于样本D，如果根据特征A的某个值，把D分成D1和D2，则在特征A的条件下，D的基尼系数为：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g9274yiwhoj30iq02wmx8.jpg)\n",
    "\n",
    "#### 4.7 ID3存在的问题\n",
    "缺点：\n",
    "- 存在偏向于选择取值较多的特征问题\n",
    "- 连续值不支持\n",
    "- 缺失值不支持\n",
    "- 无法枝剪\n",
    "\n",
    "\n",
    "#### 4.8 C4.5相对于ID3的改进点\n",
    "- 主动进行的连续的特征离散化\n",
    "    - 比如m个样本的连续特征A有m个，先set在order，再两两组合求中间值，以该值点作为划分的待选点\n",
    "    - **连续特征可以再后序特征划分中仍可继续参与计算**\n",
    "- 缺失问题优化\n",
    "    - 训练：用所有未缺失的样本，和之前一样，计算每个属性的信息增益，但是这里的信息增益需要乘以一个系数（未缺失样本/总样本）\n",
    "    - 预测：直接跳过该节点，并将此样本划入所有子节点，划分后乘以系数计算，系数为不缺失部分的样本分布\n",
    "- 采用预枝剪\n",
    "\n",
    "#### 4.9 CART的连续特征改进点\n",
    "- 分类情况下的变量特征选择\n",
    "    - 离散变量：二分划分\n",
    "    - 连续变量：和C4.5一致，如果当前节点为连续属性，则该属性后面依旧可以参与子节点的产生选择过程\n",
    "- 回归情况下，连续变量不再采取中间值划分，采用最小方差法\n",
    "\n",
    "#### 4.10 CART分类树建立算法的具体流程\n",
    "我们的算法从根节点开始，用训练集递归的建立CART树。\n",
    "- 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归\n",
    "- 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归\n",
    "- 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数\n",
    "- 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2\n",
    "- 递归1～4\n",
    "\n",
    "#### 4.11 CART回归树建立算法的具体流程\n",
    "其他部分都一样，在构建过程中遇到连续值的话，并不是利用C4.5中的中间值基尼系数的方式，而是采取了最小方差方法：\n",
    "\n",
    "对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点，其中c1为D1的均值，c2为D2的均值：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g928jep1nkj309a00q745.jpg)\n",
    "\n",
    "#### 4.12 CART输出结果的逻辑？\n",
    "- 回归树：利用最终叶子的均值或者中位数来作为输出结果\n",
    "- 分类树：利用最终叶子的大概率的分类类别来作为输出结果\n",
    "\n",
    "#### 4.13 CART树算法的剪枝过程是怎么样的？\n",
    "目标函数为：𝐶𝛼(𝑇𝑡)=𝐶(𝑇𝑡)+𝛼|𝑇𝑡|，其中，α为正则化参数，这和线性回归的正则化一样。𝐶(𝑇𝑡)为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量。|𝑇𝑡|是子树T的叶子节点的数量\n",
    "\n",
    "当𝛼=0时，即没有正则化，原始的生成的CART树即为最优子树。当𝛼=∞时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。\n",
    "当然，这是两种极端情况。一般来说，𝛼越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的𝛼，一定存在使损失函数𝐶𝛼(𝑇)最小的唯一子树。\n",
    "由枝剪到根结点及不枝剪两种情况可得：𝛼=(𝐶(𝑇)−𝐶(𝑇𝑡))/(|𝑇𝑡|−1) , C(T)为根结点误差\n",
    "\n",
    "- 计算出每个子树是否剪枝的阈值𝛼\n",
    "- 选择阈值𝛼集合中的最小值\n",
    "- 分别针对不同的最小值𝛼所对应的剪枝后的最优子树做交叉验证\n",
    "\n",
    "#### 4.14 树形结构为何不需要归一化？\n",
    "无论是分类树还是回归树，无论是连续变量还是离散变量，树模型一直想找的是最优切分点，不存在梯度导数等计算，数值缩放不影响分裂点位置，对树模型的结构不造成影响。\n",
    "\n",
    "#### 4.15 决策树的优缺点\n",
    "优点：\n",
    "- 缺失值不敏感，对特征的宽容程度高，可缺失可连续可离散\n",
    "- 可解释性强\n",
    "- 算法对数据没有强假设\n",
    "- 可以解决线性及非线性问题\n",
    "- 有特征选择等辅助功能\n",
    "\n",
    "缺点：\n",
    "- 处理关联性数据比较薄弱\n",
    "- 正负量级有偏样本的样本效果较差\n",
    "- 单棵树的拟合效果欠佳，容易过拟合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. 贝叶斯\n",
    "#### 5.1 解释一下朴素贝叶斯中考虑到的条件独立假设\n",
    "![](https://tva1.sinaimg.cn/large/006y8mN6gy1g92b15s6daj308x00rq2s.jpg)\n",
    "\n",
    "#### 5.2 讲一讲你眼中的贝叶斯公式和朴素贝叶斯分类差别\n",
    "贝叶斯公式是完整的数学公式P(A/B) = P(A)P(B/A)/P(B)\n",
    "\n",
    "朴素贝叶斯 = 贝叶斯公式 + 条件独立假设，在实际使用过程中，朴素贝叶斯完全只需要关注P(A,B)=P(A)P(B/A)即可\n",
    "\n",
    "#### 5.3 朴素贝叶斯中出现的常见模型有哪些\n",
    "- 多项式：多项式模型适用于离散特征情况，在文本领域应用广泛， 其基本思想是：我们将重复的词语视为其出现多次\n",
    "    - 因为统计次数，所以会出现0次可能，所以实际中进行了平滑操作\n",
    "        - 先验平滑：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g92bmactdlj303o0133yb.jpg)\n",
    "        - 后验平滑：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g92borlh0nj3043018q2r.jpg)\n",
    "        - 两者形式非常像，区别就在先验平滑分母考虑的是平滑类别y个数，后验平滑分母考虑的是平滑特征对应特征x可选的个数\n",
    "- 高斯：高斯模型适合连续特征情况，[高斯公式](https://github.com/sladesha/Reflection_Summary/blob/master/数学/概率密度分布/概率密度分布.md#L1)\n",
    "    - 高斯模型假设在对应类别下的每一维特征都服从高斯分布（正态分布）\n",
    "- 伯努利：伯努利模型适用于离散特征情况，它将重复的词语都视为只出现一次\n",
    "\n",
    "#### 5.4 出现估计概率值为 0 怎么处理\n",
    "拉普拉斯平滑\n",
    "\n",
    "#### 5.5 朴素贝叶斯的优缺点？\n",
    "- 优点： 对小规模数据表现很好，适合多分类任务，适合增量式训练\n",
    "- 缺点：对输入数据的表达形式很敏感（离散、连续，值极大极小之类的）\n",
    "\n",
    "#### 5.6 朴素贝叶斯与 LR 区别？\n",
    "- 生成模型和判别模型\n",
    "- 条件独立要求\n",
    "- 小数据集和大数据集\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "朴素贝叶斯算法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def NaiveBayes(xi,x,y):\n",
    "    \n",
    "    def Py(ck):\n",
    "        return np.sum(y == ck) / len(y)\n",
    "        \n",
    "    def Pxy(j,ajl,ck):\n",
    "        \n",
    "        IY = np.sum(y == ck)\n",
    "        IX = 0.\n",
    "        for i in range(len(x[:,j])):\n",
    "            if x[i,j] == ajl and y[i] == ck:\n",
    "                IX += 1\n",
    "\n",
    "        return IX / IY\n",
    "    \n",
    "\n",
    "    result = []\n",
    "    \n",
    "    for yi in np.unique(y):\n",
    "        prod = 1\n",
    "        for j in range(len(xi)):\n",
    "            prod *= Pxy(j,xi[j],yi)\n",
    "            \n",
    "        result.append([yi,prod])\n",
    "        \n",
    "    result = np.array(result)\n",
    "    return result[result[:,1].argmax(),0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.  随机森林\n",
    "#### 6.1 解释下随机森林?\n",
    "- 随机森林=bagging+决策树\n",
    "- 随机：特征选择随机+数据采样随机\n",
    "    - 特征随机是在决策树**每个结点上选择的时候随机**，并不是在每棵树创建的时候随机\n",
    "    - 每个结点上对特征选择都是从全量特征中进行采样对，**不会剔除已利用的**\n",
    "    - 数据采样，是有放回的采样\n",
    "        - 1个样本**未被选到**的概率为p = (1 - 1/N)^N = 1/e，即为OOB\n",
    "- 森林：多决策树组合\n",
    "    - 可分类可回归，回归是对输出值进行简单平均，分类是对输出值进行简单投票\n",
    "\n",
    "#### 6.2 随机森林用的是什么树？\n",
    "CART树\n",
    "\n",
    "#### 6.3 随机森林的生成过程？\n",
    "- 生成单棵决策树\n",
    "    - 随机选取样本\n",
    "    - 从M个输入特征里随机选择m个输入特征，然后从这m个输入特征里选择一个最好的进行分裂\n",
    "    - 不需要剪枝，直到该节点的所有训练样例都属于同一类\n",
    "- 生成若干个决策树\n",
    "\n",
    "#### 6.4 解释下随机森林节点的分裂策略？\n",
    "Gini系数\n",
    "\n",
    "在连续值和离散值上：[CART分类树建立算法的具体流程](https://github.com/sladesha/Reflection_Summary/blob/master/机器学习/决策树/决策树.md#L164)和[CART回归树建立算法的具体流程](https://github.com/sladesha/Reflection_Summary/blob/master/机器学习/决策树/决策树.md#L164)\n",
    "\n",
    "#### 6.5 随机森林的损失函数是什么？\n",
    "- 分类RF对应的CART分类树默认是基尼系数gini,另一个可选择的标准是信息增益\n",
    "- 回归RF对应的CART回归树默认是均方差mse，另一个可以选择的标准是绝对值差mae\n",
    "- 参考决策树的损失函数即可：[CART分类树建立算法的具体流程](https://github.com/sladesha/Reflection_Summary/blob/master/机器学习/决策树/决策树.md#L164)和[CART回归树建立算法的具体流程](https://github.com/sladesha/Reflection_Summary/blob/master/机器学习/决策树/决策树.md#L164)\n",
    "\n",
    "#### 6.6 为了防止随机森林过拟合可以怎么做?\n",
    "- 增加树的数量\n",
    "- 增加叶子结点的数据数量\n",
    "- bagging算法中，基模型的期望与整体期望一致，参考[就理论角度论证Bagging、Boosting的方差偏差问题](https://github.com/sladesha/Reflection_Summary/blob/master/基础概念/方差与偏差/方差与偏差.md#L7)\n",
    "- 随着基模型数（m）的增多，整体模型的方差减少，从而防止过拟合的能力增强，模型的准确度得到提高\n",
    "\n",
    "#### 6.7 随机森林特征选择的过程？\n",
    "特征选择方向：对于某个特征，如果用另外一个随机值替代它之后的表现比之前更差，则表明该特征比较重要，所占的权重应该较大，不能用一个随机值替代。相反，如果随机值替代后的表现没有太大差别，则表明该特征不那么重要，可有可无\n",
    "    - 通过permutation的方式将原来的所有N个样本的第i个特征值重新打乱分布（相当于重新洗牌）\n",
    "    - 是使用uniform或者gaussian抽取随机值替换原特征\n",
    "    \n",
    "#### 6.8 是否用过随机森林，有什么技巧?\n",
    "- 除了直接让随机森林选择特征，还有自行构造组合特征带入模型，是的randomForest-subspace变成randomForest-combination\n",
    "\n",
    "#### 6.9 RF的参数有哪些，如何调参？\n",
    "要调整的参数主要是 n_estimators和max_features \n",
    "- n_estimators是森林里树的数量，通常数量越大，效果越好，但是计算时间也会随之增加。 此外要注意，当树的数量超过一个临界值之后，算法的效果并不会很显著地变好\n",
    "- max_features是分割节点时考虑的特征的随机子集的大小。 这个值越低，方差减小得越多，但是偏差的增大也越多\n",
    "    - 回归：max_features = n_features\n",
    "    - 分类：max_features = sqrt(n_features)\n",
    "\n",
    "其他参数中\n",
    "- class_weight也可以调整正负样本的权重\n",
    "-  max_depth = None 和 min_samples_split = 2 结合，为不限制生成一个不修剪的完全树\n",
    " \n",
    "#### 6.10 RF的优缺点 ？\n",
    "- 优点:\n",
    "    - 不同决策树可以由不同主机并行训练生成，效率很高\n",
    "    - 随机森林算法继承了CART的优点\n",
    "    - 将所有的决策树通过bagging的形式结合起来，避免了单个决策树造成过拟合的问题\n",
    "- 缺点：\n",
    "    - 没有严格数学理论支持\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 集成学习\n",
    "    - [介绍一下Boosting的思想](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [最小二乘回归树的切分过程是怎么样的](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [有哪些直接利用了Boosting思想的树模型](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [gbdt和boostingtree的boosting分别体现在哪里](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [gbdt的中的tree是什么tree？有什么特征](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [常用回归问题的损失函数](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [常用分类问题的损失函数](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [什么是gbdt中的残差的负梯度](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [如何用损失函数的负梯度实现gbdt](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [拟合损失函数的负梯度为什么是可行的](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [即便拟合负梯度是可行的，为什么不直接拟合残差？ 拟合负梯度好在哪里](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [Shrinkage收缩的作用](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [feature属性会被重复多次使用么](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [gbdt如何进行正则化的](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [为什么集成算法大多使用树类模型作为基学习器？或者说，为什么集成学习可以在树类模型上取得成功](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [gbdt的优缺点](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [gbdt和randomforest区别](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [GBDT和LR的差异](机器学习/集成学习/GBDT.md#L164)\n",
    "    - [xgboost对比gbdt/boosting Tree有了哪些方向上的优化](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost和gbdt的区别](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost优化目标/损失函数改变成什么样](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost如何使用MAE或MAPE作为目标函数](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost如何寻找分裂节点的候选集](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost如何处理缺失值](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost在计算速度上有了哪些点上提升](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost特征重要性是如何得到的](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xGBoost中如何对树进行剪枝](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xGBoost模型如果过拟合了怎么解决](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [xgboost如何调参数](机器学习/集成学习/Xgboost.md#L164)\n",
    "    - [XGboost缺点](机器学习/集成学习/LightGBM.md#L164)\n",
    "    - [LightGBM对Xgboost的优化](机器学习/集成学习/LightGBM.md#L164)\n",
    "    - [LightGBM亮点](机器学习/集成学习/LightGBM.md#L164)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- FM/FFM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9. SVM\n",
    "#### 9.1 简单介绍SVM?\n",
    "- 从分类平面，到求两类间的最大间隔![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93fr1xbmyj3034018mwy.jpg)，到转化为求间隔分之一等优化问题：loss=min(1/2·||W||·||W||)  subject to：y(wx+b)>=1，其中||·||为2范数\n",
    "- 然后就是优化问题的解决办法，首先是用拉格拉日乘子把约束优化转化为无约束优化，对各个变量求导令其为零，得到的式子带入拉格朗日式子从而转化为对偶问题\n",
    "- 最后再利用SMO（序列最小优化）来解决这个对偶问题\n",
    "\n",
    "#### 9.2 什么叫最优超平面？\n",
    "- 两类样本分别分割在该超平面的两侧\n",
    "- 超平面两侧的点离超平面尽可能的远\n",
    "\n",
    "#### 9.3 什么是支持向量？\n",
    "在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。换句话说，就是超平面附近决定超平面位置的那些参与计算锁定平面位置的点\n",
    "\n",
    "#### 9.4 SVM 和全部数据有关还是和局部数据有关?\n",
    "局部\n",
    "\n",
    "#### 9.5 加大训练数据量一定能提高SVM准确率吗？\n",
    "支持向量的添加才会提高，否则无效\n",
    "\n",
    "#### 9.6 如何解决多分类问题？\n",
    "对训练器进行组合。其中比较典型的有一对一，和一对多\n",
    "\n",
    "#### 9.7 可以做回归吗，怎么做？\n",
    "可以，把loss函数变为：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93jrdscfrj309l011dfo.jpg)\n",
    "\n",
    "#### 9.8 SVM 能解决哪些问题？\n",
    "- 线性问题\n",
    "    - 对于n为数据，找到n-1维的超平面将数据分成2份。通过增加一个约束条件： 要求这个超平面到每边最近数据点的距离是最大的\n",
    "- 非线性问题\n",
    "    -  SVM通过结合使用拉格朗日乘子法和KTT条件，以及核函数可以用smo算法解出非线性分类器\n",
    "\n",
    "#### 9.9 介绍一下你知道的不同的SVM分类器？\n",
    "- 硬SVM分类器（线性可分）：当训练数据可分时，通过间隔最大化，直接得到线性表分类器\n",
    "- 软SVM分类器（线性可分）：当训练数据近似可分时，通过软间隔最大化，得到线性表分类器\n",
    "- kernel SVM：当训练数据线性不可分时，通过核函数+软间隔的技巧，得到一个非线性的分类器\n",
    "\n",
    "#### 9.10 什么叫软间隔？\n",
    "软间隔允许部分样本点不满足约束条件： 1<y(wx+b)\n",
    "\n",
    "#### 9.11 SVM 软间隔与硬间隔表达式\n",
    "- 硬间隔： ![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93ha4y4glj3094011a9w.jpg)\n",
    "- 软间隔： ![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93hae5o8lj30d701f0sn.jpg)\n",
    "\n",
    "\n",
    "#### 9.12 SVM原问题和对偶问题的关系/解释原问题和对偶问题？\n",
    "- svm原问题是：求解![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93fy1gm79j309b0173yd.jpg)\n",
    "- svm对偶问题：求解![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93g16v0syj309d01gglh.jpg)\n",
    "    - 拉格朗日乘子法：求f的最小值时，有h=0的限制条件，那么就构造∑λh+f=Loss,作为新loss \n",
    "    - 引入松弛变量α的目的是构造满足拉格朗日条件的限制性条件\n",
    "    - 在对原来的w求偏导之外再对新构造的乘子λ和松弛变量α求偏导数\n",
    "\n",
    "#### 9.13 为什么要把原问题转换为对偶问题？\n",
    "- 因为原问题是带有限制性条件的凸二次规划问题不方便求解，转换为对偶问题更加高效\n",
    "- 引入了核函数\n",
    "\n",
    "#### 9.14 为什么求解对偶问题更加高效？\n",
    "- 原问题是要考虑限制性条件的最优，而对偶问题考虑的是类似分情况讨论的解析问题\n",
    "- 因为只用求解alpha系数，而alpha系数只有支持向量才非0，其他全部为0\n",
    "\n",
    "#### 9.15 alpha系数有多少个？\n",
    "样本点的个数\n",
    "\n",
    "#### 9.16 KKT限制条件，KKT条件有哪些，完整描述\n",
    "- ![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93g16v0syj309d01gglh.jpg)分别对原来的w求偏导之外再对新构造的乘子λ和松弛变量α求偏导数，并且都等于0后的联立方程便是不等式约束优化优化问题的 KKT(Karush-Kuhn-Tucker) 条件\n",
    "- KKT乘子λ>=0\n",
    "\n",
    "#### 9.17 引入拉格朗日的优化方法后的损失函数解释\n",
    "- 原损失函数：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93fy1gm79j309b0173yd.jpg)\n",
    "- 优化后的损失函数：![](https://tva1.sinaimg.cn/large/006y8mN6gy1g93gp9vlbjj30c401gt8m.jpg)\n",
    "    - 要求KKT乘子λ>=0\n",
    "\n",
    "#### 9.18 核函数的作用是啥\n",
    "核函数能够将特征从低维空间映射到高维空间， 这个映射可以把低维空间中不可分的两类点变成高维线性可分的\n",
    "\n",
    "#### 9.19 核函数的种类和应用场景\n",
    "- 线性核函数：主要用于线性可分的情形。参数少，速度快。\n",
    "- 多项式核函数：\n",
    "- 高斯核函数：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。\n",
    "- sigmoid 核函数：\n",
    "- 拉普拉斯核函数：\n",
    "\n",
    "#### 9.20 如何选择核函数\n",
    "我用的比较多的是线性核函数和高斯核函数，线性用于特征多，线性问题的时候，高斯核函数用于特征少，非线性问题需要升维的时候\n",
    "\n",
    "#### 9.21 常用核函数的定义？\n",
    "在机器学习中常用的核函数，一般有这么几类，也就是LibSVM中自带的这几类：\n",
    "1) 线性：K(v1,v2) = <v1,v2>\n",
    "2) 多项式：K(v1,v2) = (r<v1,v2>+c)^n\n",
    "3) Radial basis function：K(v1,v2) = exp(-r||v1-v2||^2)\n",
    "4) Sigmoid：tanh(r<v1,v2>+c)\n",
    "\n",
    "#### 9.22 核函数需要满足什么条件？\n",
    "Mercer定理：核函数矩阵是对称半正定的\n",
    "\n",
    "#### 9.23 为什么在数据量大的情况下常常用lr代替核SVM？\n",
    "- 计算非线性分类问题下，需要利用到SMO方法求解，该方法复杂度高O(n^2)\n",
    "- 在使用核函数的时候参数假设全靠试，时间成本过高\n",
    "\n",
    "#### 9.24 高斯核可以升到多少维？为什么\n",
    "无穷维\n",
    "e的n次方的泰勒展开得到了一个无穷维度的映射\n",
    "\n",
    "#### 9.25 SVM和逻辑斯特回归对同一样本A进行训练，如果某类中增加一些数据点，那么原来的决策边界分别会怎么变化？\n",
    "如果在svm容忍范围内或者在svm的margin外，则不受影响；否则决策边界会发生调整\n",
    "\n",
    "#### 9.26 各种机器学习的应用场景分别是什么？例如，k近邻,贝叶斯，决策树，svm，逻辑斯蒂回归\n",
    "- 线性问题：\n",
    "    - 线性：\n",
    "        - 逻辑回归，线性svm\n",
    "    - 非线性：\n",
    "        - 贝叶斯，决策树，核svm，DNN\n",
    "- 数据问题：\n",
    "    - 数据量大特征多：\n",
    "        - 逻辑回归\n",
    "        - 决策树算法\n",
    "    - 数据量少特征少：\n",
    "        - 核svm\n",
    "- 缺失值多：\n",
    "    - 树模型\n",
    "\n",
    "#### 9.27 Linear SVM 和 LR 有什么异同？\n",
    "- LR是参数模型，SVM为非参数模型。\n",
    "- LR采用的损失函数为logisticalloss，而SVM采用的是hingeloss。\n",
    "- 在学习分类器的时候，SVM只考虑与分类最相关的少数支持向量点。\n",
    "- LR的模型相对简单，在进行大规模线性分类时比较方便。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SVM算法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SVM:\n",
    "    def __init__(self, max_iter=100, kernel='linear'):\n",
    "        self.max_iter = max_iter\n",
    "        self.kernel = kernel\n",
    "\n",
    "    def init_args(self, features, labels):\n",
    "        self.m, self.n = features.shape\n",
    "        self.X = features\n",
    "        self.Y = labels\n",
    "        self.b = 0.0\n",
    "\n",
    "        # 将Ei保存在一个列表里\n",
    "        self.alpha = np.ones(self.m)\n",
    "        self.E = [self._E(i) for i in range(self.m)]\n",
    "        # 松弛变量\n",
    "        self.C = 1.0\n",
    "\n",
    "    def _KKT(self, i):\n",
    "        y_g = self._g(i) * self.Y[i]\n",
    "        if self.alpha[i] == 0:\n",
    "            return y_g >= 1\n",
    "        elif 0 < self.alpha[i] and self.alpha[i] < self.C:\n",
    "            return y_g == 1\n",
    "        else:\n",
    "            return y_g <= 1\n",
    "\n",
    "    # g(x)预测值，输入xi（X[i]）\n",
    "    def _g(self, i):\n",
    "        r = self.b\n",
    "        for j in range(self.m):\n",
    "            r += self.alpha[j] * self.Y[j] * self._kernel(self.X[i], self.X[j])\n",
    "        return r\n",
    "\n",
    "    # 核函数\n",
    "    def _kernel(self, x1, x2):\n",
    "        if self.kernel == 'linear':\n",
    "            return (x1 * x2).sum()\n",
    "        elif self.kernel == 'poly':\n",
    "            p = 2\n",
    "            return ((x1 * x2).sum() + 1) ** p\n",
    "        elif self.kernel == \"Gaussian\":\n",
    "            return np.exp(-1 * ((x1 - x2) * (x1 - x2)).sum() / (2 * self.sigma ** 2))\n",
    "        return 0\n",
    "\n",
    "    # E（x）为g(x)对输入x的预测值和y的差\n",
    "    def _E(self, i):\n",
    "        return self._g(i) - self.Y[i]\n",
    "    \n",
    "    def _init_alpha(self):\n",
    "#         其实就是选取第一分量和第二分量\n",
    "        for i in range(self.m):\n",
    "            if self._KKT(i):\n",
    "                continue\n",
    "\n",
    "            E1 = self.E[i]\n",
    "            # 如果E2是+，选择最小的；如果E2是负的，选择最大的\n",
    "            if E1 >= 0:\n",
    "                j = min(range(self.m), key=lambda x: self.E[x])\n",
    "            else:\n",
    "                j = max(range(self.m), key=lambda x: self.E[x])\n",
    "            return i, j\n",
    "\n",
    "    def _compare(self, _alpha, L, H):\n",
    "        if _alpha > H:\n",
    "            return H\n",
    "        elif _alpha < L:\n",
    "            return L\n",
    "        else:\n",
    "            return _alpha\n",
    "        \n",
    "    def fit(self, features, labels):\n",
    "        self.init_args(features, labels)\n",
    "\n",
    "        for t in range(self.max_iter):\n",
    "            # train\n",
    "            i1, i2 = self._init_alpha()\n",
    "\n",
    "            # 边界\n",
    "            if self.Y[i1] == self.Y[i2]:\n",
    "                L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)\n",
    "                H = min(self.C, self.alpha[i1] + self.alpha[i2])\n",
    "            else:\n",
    "                L = max(0, self.alpha[i2] - self.alpha[i1])\n",
    "                H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])\n",
    "\n",
    "            E1 = self.E[i1]\n",
    "            E2 = self.E[i2]\n",
    "            # eta=K11+K22-2K12\n",
    "            eta = self._kernel(self.X[i1], self.X[i1]) + self._kernel(self.X[i2], self.X[i2]) - 2 * self._kernel(self.X[i1], self.X[i2])\n",
    "            if eta <= 0:\n",
    "                # print('eta <= 0')\n",
    "                continue\n",
    "\n",
    "            alpha2_new_unc = self.alpha[i2] + self.Y[i2] * ( E1 - E2) / eta  #此处有修改，根据书上应该是E1 - E2，书上130-131页\n",
    "            alpha2_new = self._compare(alpha2_new_unc, L, H)\n",
    "\n",
    "            alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * ( self.alpha[i2] - alpha2_new)\n",
    "\n",
    "            b1_new = -E1 - self.Y[i1] * self._kernel(self.X[i1], self.X[i1]) * (\n",
    "                alpha1_new - self.alpha[i1]) - self.Y[i2] * self._kernel(  self.X[i2],self.X[i1]) * (alpha2_new - self.alpha[i2]) + self.b\n",
    "            b2_new = -E2 - self.Y[i1] * self._kernel(self.X[i1], self.X[i2]) * (\n",
    "                alpha1_new - self.alpha[i1]) - self.Y[i2] * self._kernel(\n",
    "                    self.X[i2], self.X[i2]) * (alpha2_new - self.alpha[i2]) + self.b\n",
    "\n",
    "            if 0 < alpha1_new  < self.C:\n",
    "                b_new = b1_new\n",
    "            elif 0 < alpha2_new < self.C:\n",
    "                b_new = b2_new\n",
    "            else:\n",
    "                # 选择中点\n",
    "                b_new = (b1_new + b2_new) / 2\n",
    "\n",
    "            # 更新参数\n",
    "            self.alpha[i1] = alpha1_new\n",
    "            self.alpha[i2] = alpha2_new\n",
    "            self.b = b_new\n",
    "\n",
    "            self.E[i1] = self._E(i1)\n",
    "            self.E[i2] = self._E(i2)\n",
    "        return 'train done!'\n",
    "    \n",
    "    def _weight(self):\n",
    "        # linear model\n",
    "        yx = self.Y.reshape(-1, 1) * self.X\n",
    "        self.w = np.dot(yx.T, self.alpha)\n",
    "        return self.w"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
